package my.suveng.struct.heap;

/**
 * 最大堆实现
 * @author suwenguang
 **/
public class MaxHeap implements IHeap {

    private final IHeapElement[] elements;

    private int size;

    private final int capacity;

    public MaxHeap(int capacity) {
        if (capacity < 0) {
            throw new RuntimeException("构建失败");
        }
        this.capacity = capacity;
        this.elements = new IHeapElement[capacity];
    }

    /**
     * 增加
     * 1. 在最后增加节点
     * 2. 上浮比较
     *
     * @author suwenguang
     */
    public void push(IHeapElement x) {
        if (size >= capacity) {
            throw new RuntimeException("插入失败, 堆已满");
        }
        //添加在树中最后一个节点
        elements[size] = x;
        int currIndex = size;
        int parentIndex = (size - 1) / 2;
        // 不断和父节点比较
        while (currIndex > 0 && elements[currIndex].compareTo(elements[parentIndex]) > 0) {
            // 如果大于则互换位置
            IHeapElement temp = elements[currIndex];
            elements[currIndex] = elements[parentIndex];
            elements[parentIndex] = temp;
        }

        // 维护size
        size++;
    }

    /**
     * 1. 删除顶部节点
     * 2. 下沉比较
     * 下沉到没有子节点为止
     * @author suwenguang
     */
    public void pop() {
        int currIndex = 0;
        elements[currIndex] = elements[size - 1];
        size--;

        int sub = (currIndex + 1) * 2;
        while (sub < size) {
            if (elements[sub].compareTo(elements[sub - 1]) > 0) {
                IHeapElement temp = elements[currIndex];
                elements[currIndex] = elements[sub];
                elements[sub] = temp;
                currIndex = sub;
            } else {
                IHeapElement temp = elements[currIndex];
                elements[currIndex] = elements[sub - 1];
                elements[sub - 1] = temp;
                currIndex = sub - 1;
            }
            sub = (currIndex + 1) * 2;
        }

        // 处理只有左子节点
        if (sub - 1 < size) {
            if (elements[currIndex].compareTo(elements[sub - 1]) < 0) {
                IHeapElement temp = elements[currIndex];
                elements[currIndex] = elements[sub - 1];
                elements[sub - 1] = temp;
            }
        }

    }

    public IHeapElement max() {
        return elements[0];
    }


}
